#!/usr/bin/python
# Reads FIMI file from stdin and hashes its pairs, keeping for each
# hash value a "SpaceSaving" data structure that computes the most frequent pair,
# assuming that it occurs at least 50% of the time.
# The output is a list of pairs, with upper and lower bounds on frequency.
# Optionally: Compute just part of the hash table, [<range start>;<range end>[
# gunzip -c data/[datafile] | python workspace/pairse.py 100 output/[output file]

# Example: gunzip -c data/mushroom_test.dat.gz | python workspace/pairse.py 1 output/mushroom_test.pairs

import sys,math,random,time

initTime = time.time()

if (len(sys.argv) <= 2):
	print "Syntax: pairse.py <tablesize> <outputfile> [<range start> <range end>]"
	exit(0)

size = int(sys.argv[1])

if (len(sys.argv) >= 5):
	(rstart,rend) = (int(sys.argv[3]),int(sys.argv[4]))
else:
	(rstart,rend) = (0,size)

hashtable = [((0,None,0),(0,None,0))] * (rend-rstart) # space saving sketc hwith 2 elements
print len(hashtable)
# ((count1,pair1,eps1),(count2,pair2,eps2)); invariant: count1>=count2
h1 = {} # mapping (x, h(x))
h2 = {}

def val(h,x):
	if not(x in h):
		random.seed(x) # http://docs.python.org/library/random.htm. Hashvalue of x is determined by the random.seed
		h[x] = int(random.random()*size)
	return h[x]

def traverseline(start,offset):
	j = start
	if (v1+h2val[j][0]<rstart+offset): return # Nothing in this line. Sum of hashvalue below lower limit

	while (j<len(h2val)) and (v1+h2val[j][0]<rend+offset): # check interval [q,r) [q+k, q+r)
		(v2,x2) = h2val[j] # v2 = hashvalue, x2 = value of element
		if x1<x2: # x1 = value of ith el in A. defined below.
			h = v1+v2-offset-rstart # hashfunction h = h1 + h2, also independent
			#print h,v1,v2,offset,rstart
			((count1,pair1,eps1),(count2,pair2,eps2)) = hashtable[h]      # fetch the pairs in the bucket
			if (x1,x2)==pair1: count1+=1                                  # check whther the pair is monitored here (increment counter)
			elif (x1,x2)==pair2: count2+=1                                # xor here (increment the counter)
			else: (count2,pair2,eps2)=(count2+1,(x1,x2),count2)           # pair not monitored => insert it and update counters
			if (count2>count1): # Maintain invariant                      # minimum count must be the second pair in the bucket
				((count1,pair1,eps1),(count2,pair2,eps2)) = ((count2,pair2,eps2),(count1,pair1,eps1))
			hashtable[h] = ((count1,pair1,eps1),(count2,pair2,eps2))
			#print (x1,x2), h, hashtable[h]
		j+=1
	return

m=0
for line in sys.stdin:
	#m = m+1
	#if (m%1000)==0:
	#	print m
	#	sys.stdout.flush()
	(h1val, h2val) = ([],[]) # list of tuples: (hashvalue of x, x)
	for item in line.split(" "):                          # for each item in transaction
		if item.rstrip().isdigit():                   # if the item is a number
			x = int(item)                         # call item "x"
			h1val.append((val(h1,x),x))           # compute hash value h1(x)
			h2val.append((val(h2,x+0.5),x))       # compute hash value h2(x)

	#print ("h1: ")
	#print (h1val)
	#print ("h2: ")
	#print (h2val)
	h1val.sort()                                          # sort the hash values in the first list by hash value
	h2val.sort()                                          # sort the hash values in the second list by hash value
	(jstart1,jstart2) = (len(h2val)-1,len(h2val)-1)       # this are placeholders for starting positions. iterators
	for i in xrange(0,len(h1val)):                        # for each havalue in first list. xrange() "lazy" sequence
		(v1,x1) = h1val[i]                            # consider the i-th element x,h1(x)
		# v1 = hashvalue of x, x1 = value of x
		# h2val[jstart1-1][0] is hashvalue of jth el
		while (jstart1>0) and (v1+h2val[jstart1-1][0] >= rstart): jstart1-=1                 # look for the position where the sum is in [i,j) (though, why jstart1-1?)
		while (jstart2>0) and (v1+h2val[jstart2-1][0] >= size+rstart): jstart2-=1            # look for the position where the sum is in [i+k,j+k) (though, why jstart2-1?)
		#print jstart1, jstart2
		traverseline(jstart1,0)                       # produce the pairs
		traverseline(jstart2,size)                    # produce the pairs

result = []
print len(hashtable)
for ((count1,pair1,eps1),(count2,pair2,eps2)) in hashtable:
	if pair1!=None:
		result.append((count1-eps1,count1,pair1))

result.sort()
result.reverse()

fout = open(sys.argv[2],'w')
for (lower,upper,(x1,x2)) in result:
	fout.write(str(lower)+" "+str(upper)+":"+str(x1)+"<->"+str(x2)+"\n")
fout.close()

#print (hashtable)
print((time.time() - initTime)*1000)

# Graph for Mathematica input:
# cut -d : -f 2  mushroom.pairs | paste -s -d ',' -
# Weighted graph: - Method -> {"SpringElectricalEmbedding", "RecursionMethod" -> {"Multilevel", "CoarseningScheme" -> "MaximalIndependentEdgeSetHeavyEdge"}}